The present invention relates to systems and methods for decoding data, and more particularly, to systems and methods for decoding information additive codes and multi-stage information additive codes, herein referred to collectively as “chain reaction codes.”
Chain reaction codes have been described previously in the assignee's patents, such as U.S. Pat. No. 6,307,487 entitled “Information Additive Code Generator and Decoder for Communication Systems” (hereinafter “Luby I”), and U.S. patent application Ser. No. 10/032,156, entitled “Multi-Stage Code Generator and Decoder for Communication Systems” (hereinafter “Raptor”). As described therein, chain reaction decoding is a unique form of forward error-correction that enables data reconstruction from a received data set of a given size, without regard to the particular data packets received. Communication systems employing chain reaction codes are able to communicate information much more efficiently compared to traditional FEC codes transmitted via data carousel or acknowledgement-based protocols, as described in Luby I or Raptor.
FIG. 1 illustrates an exemplary process of encoding data using chain reaction codes in which an output symbol 170 is generated from several input symbols. The input symbols are denoted 110(a)-110(f). In some embodiments the first step of the coding process is static encoding, as described in Raptor. This step may produce the source symbols, denoted 120(a)-120(f), and 160(a)-160(c). In some embodiments, static encoding may be systematic, so that the values of the source symbols 120(a)-120(f) are equal to those of 110(a)-110(f). In some embodiments, there may be no static encoding, in which case the input symbols coincide with the source symbols.
Once the source symbols have been created, the output symbols are generated from the source symbols. Hereinafter, an output symbol and an input symbol are described as “associated” if the value of the input symbol is used to obtain the value of the output symbol. The mathematical operation which defines this association may be any particular operation, and in one embodiment, the output symbol's value is the XOR of the values of some of the source symbols. For each output symbol, key generator 140 produces a key, from which the weight of the output symbol is determined from a weight table 150. Once the weight W is determined, W random or pseudorandom source symbols are chosen, and the value of the output symbol is computed as the XOR of the values of these source symbols. For example, in FIG. 1, the weight of the output symbol 170 is equal to 3 and its value is determined as the XOR of the source symbols 120(a), 120(d), and 160(b). Correspondingly, output symbol 170 is associated to the source symbols 120(a), 120(d), and 160(b). Hereinafter, the term “degree” is used synonymously with “weight.”
FIG. 2A illustrates a decoding graph used in the decoding of a chain reaction code. This decoding graph consists of two sets of symbols, the source symbols 220 (a)-(i), and the output symbols 230 (a)-(l). An output symbol is connected to a source symbol if the source and output symbols are “associated,” as described above
FIG. 2B illustrates a decoding matrix corresponding to the decoding graph of FIG. 2A which is useful in the decoding process. The decoding matrix 200 has as many rows as there are output symbols, as many columns as there are source symbols, and is populated with entries “0” and “1”. A “1” is entered at position (k,j) of the decoding matrix if the jth source symbol is associated with the kth output symbol.
In a typical chain reaction decoding process, decoding starts by identifying an output symbol O1 associated with a single source symbol. The term “output symbol of degree one” refers to the aforementioned output symbol associated with only one source symbol. Similarly, an output symbol associated with two source symbols would be referred to as an output symbol of “degree two.” Source symbols are referred to in a similar manner corresponding to the number of output symbols each source symbol is associated with.
Once the output symbol O1 of degree one is identified, the associated source symbol of O1 is recovered and is removed from the decoding graph. The process continues by identifying another output symbol O2 of degree one. For example, in the situation depicted in FIG. 2, O1 could be the output symbol denoted 230(a). Once its associated source symbol 220(b), is removed from the Decoding Graph, there are three output symbols of degree one, namely 230(c), 230(d), and 230(k).
The process is continued until all the source symbols are recovered, or until there is no output symbol of degree one. For example, in the situation of FIG. 2, the following sequence of output symbols are chosen to recover the corresponding source symbols:
Output symbolRecovered source symbol230(a)220(b)230(c)220(e)230(h)220(h)230(d)220(i)230(i)220(d)230(b)220(a)230(j)220(f)230(g)220(g)230(e)220(c)In this case decoding is successful.
The foregoing chain reaction decoding process encounters difficulty when no output symbol of degree one is found. In some instances, the decoding process may stop prematurely and the decoder may flag an error. Alternatively, the decoder may use other more elaborate algorithms like Gaussian elimination to complete decoding, if possible. However, the running time of Gaussian elimination may be prohibitively large for applications where fast decoding is desired, especially when the number of unrecovered input symbols at the time when no more output symbols of degree one are found is large. This would lead to a decoding algorithm whose computational overhead is substantially larger than a chain reaction decoder, and may therefore be undesirable in certain applications.
For this reason, the design of chain reaction coding systems usually is done in such a way to guarantee that the decoder does not stop prematurely. This requirement may put stringent conditions on the design of the chain reaction code than may be possible using a more complex decoder. For example, it may enforce the average degree of an output symbol to be higher than otherwise, and thus may lead to a decrease in the performance of the encoder and of the decoder. More generally, this decoding procedure forces the design of the weight table to be in such a way as to guarantee the success of the abovementioned decoding algorithm with high probability, and hence may put restrictions on the set of possible weight tables.
What is therefore needed is a new decoding algorithm that offers similar computational advantages as the chain reaction decoder, and is able to continue decoding even if no output symbol of degree one is found at some stage of the decoding.